package DataStr.practice;

public class LinkList<T> {
    //<T>泛型类型参数，用于定义类，接口或方法
    // LinkList可以处理任何类型的数据，无论是字符串，整数还是其他对象都可以用LinkList管理
    //T是一个占位符，通常用来表示任意类型
    private Node head;//记录链表的头结点
    private int N;//记录链表的长度
    private class Node{//创建节点内部类
        //存储数据
        T item;
        //下一个节点
        Node next;
        public Node(T item,Node next){
            //构造方法初始化指针
            this.item=item;
            this.next=next;
        }
    }
    public LinkList(){
        //初始化头结点，将里面的数据和下一个节点设为null，方便后面
        this.head=new Node(null,null);
        //初始化元素个数
        this.N=0;
    }
    //控制线性表
    public void clear(){
        this.head=null;
    }
    //判断线性表是否为空，是返回true，否返回false
    public boolean isEmpty(){
        if(N==0){
            return true;
        }else
            return false;
    }
    //获取线性表中元素的个数
    public int length(){
        return N;
    }
    //读取并返回线性表中的第i个元素的值
    public T get(int i){
        //通过循环，从头结点开始往后找，一次找i次，就可以找到对应的元素
        Node p=head;
      for(int index=0;index<i;index++){
          p=p.next;
      }
      return p.item;
    }
    //往线性表中添加一个元素t
    public void insert(T t){
        Node p=head;
        //找到当前最后一个节点
        while(p!=null){
            p=p.next;
        }
        //创建新节点，保存元素t
        Node newNode=new Node(t,null);//因为是最后一个节点，新添加节点next为null
        //让当前最后一个节点指向新节点
        p.next=newNode;
        //元素的个数＋1
        N++;
    }
    //在线性表的第i个元素之前插入一个值为t的数据元素
    public void insert(int i,T t){
        Node p=head;
        //找到i位置之前的一个节点
        for(int index=0;index<i-1;index++){
            p=p.next;
        }
        //找到i位置的节点
        Node current=p.next;
        //创建新节点，并且新节点需要指向原来i位置的节点
        Node newNode=new Node(t,current);
        //原来i位置的前一个结点指向新节点即可
        p.next=newNode;
        //元素个数加一
        N++;
    }
    //删除并返回线性表中第i个数据元素
    public T remove(int i){
        //找到第i个元素之前的元素
        Node p=head;
        for(int index=0;index<i-1;index++){
            p=p.next;
        }
        //找到i的元素
        Node newNode=p.next;
        //找到i之后的元素（i-1）
        Node current=newNode.next;
        //将i-1个元素连接到i之后的元素
        p.next=current;
        N--;
        return current.item;
    }
    //查找元素t在链表中第一次出现的位置
    public int indexOf(T t){
        //从头结点开始，依次找到每一个结点，取出item，和t比较，如果相同返回i否则返回-1
        Node p=head;
        for(int i=0;p.next!=null;i++){
            p=p.next;
            if(p.item.equals(t)){
                return i;
            }
        }
        return -1;
    }
}
